The industrial boom in the demands for faster microprocessors has prompted microprocessor makers to shift the design of scalar pipelined processors to higher performance superscalar processors. The scalar pipelined processors, such as the Intel.RTM. 486 and MIPS.RTM. 3000, execute each instruction in a pipelined order and disallow out-of-order execution of instructions. High performance superscalar processors, such as the Intel.RTM. Pentium Pro, Motorola.RTM. PowerPC 604, and UltraJava by Sun Microelectronic, have displaced the previous scalar pipelined processors by providing the capability of executing out-of-order instructions in parallelism. Previous superscalar processors are registered-based in which the registers in a superscalar processor can be accessed randomly. In modern trend, the UltraJava-class microprocessors are implemented in stack-based designs in which the registers must be accessed with respect to a stack top location. Superscalar processors have multiple execution units and are designed based on a plurality of registers irrespective of superscalar processors that compute instructions as registers-based or stack-based stacks.
Stacks can be used to store intermediate evaluation results, return addresses, or local variables and subroutine parameters. An example of a stack-based instruction is a last-in-first-out (LIFO) stack management scheme which saves information in a temporary storage location for common computer operations, such as mathematical expression evaluations and subroutine callings. One advantage of designing a system with a stack-based processor is that the stack-based processor uses high code density while requires small program size, resulting in the adoption of zero-operand stack-based instruction sets that disallow any operand to be associated with an opcode. To phrase it in another way, all operations are implicitly specified to be performed at a top of the stack (TOS), also referred to as a stack top location.
Superscalar stack-based processors execute each instruction by accessing the data at the TOS as stored from the previous instruction. This dependency on the necessity to access the TOS in order to execute every execution undermines the effectiveness of pipelining instructions. In effect, a subsequent instruction cannot begin until the previous instruction has been executed, which potentially could cause pipeline data hazards. Thus, the inherent nature of the frequent access to the TOS in stack-based instructions results in heavy inter-instruction data dependency, particularly among adjacent instructions.
Accordingly, it is desirable to have methods and systems which explore instruction-level parallelism by renaming stack entries in superscalar processors.